Dimensionality Reduction

PyData Cluj-Napoca meetup 3, 2019.05.07

What is dimensionality reduction

- a loose definition
- the lower dimensionality representation is sometimes called the latent space and it can differ depending on the algorithm and targeted outcomes
- in the given example we have shapes, color, transparency level, orientation. Some attributes are irrelevant, maybe we need to count by shapes, or maybe the color matters
- or maybe both, as together they can be seen as generating factors. We can reconstruct the original data having "external knowledge" about how it should look like, since we know to draw a corresponding 3D shape with a certain orientation etc.
- one difference between standard dimensionality reduction algorithms and autoencoders: AEs are models that can embed a lot of knowledge
- book example: an encoder could transform a page of text from a book to a single feature, the page number, which is easily decoded if someone else has the same book
- multiple ways of doing dimensionality reduction, from projecting points from an euclidean space to a plane, to the quest of extracting complex generative factors, like in the case of variational autoencoders

Retaining relevant data from a [large] set of features,

projecting to a lower dimensional feature subspace without losing important information

depending on the problem to be solved.

Summary

brief look at PCA (to know what we are talking about)
why dimensionality reduction
feature selection
supervised feature extraction: LDA, QDA
unsupervised feature extraction: PCA, sparse PCA, kernel PCA, ICA
non-linear dimensionality reduction: MDS, IsoMap, LLE, LLSTA, SOM
[mainly] visualization: t-SNE, UMAP
autoencoders: deep, sparse, stacked, contractive, denoising, recurrent, VAE, beta-VAE, UAE
adversarial networks: cVAEGAN

PCA

- finds a linear transformation of the input data such that the new frame of reference "better explains the data"

- what does it mean to better explain the data "in general" is an open question and depends on the problem you're trying to solve
- what it means in PCA's case is that it will transform the frame of reference, rotating the axis (and thus the input data) in such a way that most of the variance will be explained by the first axis, then by the other orhtonormal axes in decreasing order. Height+age for students versus height+age in all population
- example with people's height, weight and body mass index. Given the correlation, probably the 1st component is a combination of the inputs and something unrelated to humanly interpretable physical trait, and the 3rd component will be close to noise
- if we drop one of the components and keep only the first two, we can reduce dimensionality while (probably) still retaining most of the information in the original data. PCA has an assumption of linearity, works best when variance is equal and nicely distributed. And is sensitive to outliers
- linear regression is finding a linear relation between a target variable and a predictor, in 2D finding the line that is minimizing the distance between the line and the value of the response variable
- PCA finds as the first component the line that is minimizing the orthogonal distances to it. Minimum potential energy: rubber band example.
- bottom examples: represent our data in the new coordinate space or discard components, reduce dimensionality and represent the data as points on a line - works with classical euclidian variance (square of the distance), similarly to linear regression. Other measures of variance

Principal Component Analysis (PCA)

- generated an 8-dimensional dataset from the points on the left plot
- PCA is able to reconstruct a rotation of the source signal in the first 2 components

- example of reducing the number of dimensions by dropping redundant components. Removes redundant information while still catching most important features
- an 8-dim dataset was generated from the 2D source (left figure), adding 4 new dimensions that are linear combinations of the first with some additional noise, 1 dimension a quadratic function and 1 just noise
- we run PCA on this 8-dimensional data and dropped 6 of the components, keeping only the first two
- PCA finds a rotation of that 8-dimensional data such that if we keep only the 2 most important features (by PCA standards), we obtain something that is reconstructing the original signal quite well
- example visualizes the same dataset on which we run PCA. For the sake of exemplification it's ok anyway, but normally you should go with the train set/test set split, because real life problems are always working with unseen data
- PCA and few other algorithms are not in danger of overfitting, but you still have to worry for how representative was the sampling on which you trained
- the first principal component explains the highest variance/direction of variance
- dropping some components means to drop some variation (might be noise or relevant signal)

Why dimensionality reduction

When:
- lots of dimensions
- multiple time series with common underlying factors

Why:
- exploratory data analysis
- visualizations
- extraction of underlying (or relevant) factors
- better data separability, informative clustering
- robust learning, less overfitting, improved supervised or unsupervised models performance
- noise reduction
- anomaly detection
- data compression
- less computational resources

Why dimensionality reduction

- extraction of underlying factors: various "input features" are just measurements which can reflect the same underlying (maybe hidden) factors. Sometimes we can extracts those factors or get better combined measurements

- PCA on 9 timeseries with US stock prices over the past 3 years, 5 banks and 4 oil companies
- one datapoint for each day and 9 values for each datapoint, telling us how much the price went down or up for each stock, then we look at the first 2 principal components
- top-left corner: a plot of their cummulative return
- PCA was run on the daily returns and kept only the first two components that resulted. So we converted the activity of 9 stocks into 2 factors. Athough the principal components plot is close to noise, their cummulative form "make sense" (they have a relation with time)
- top row contains handcrafted factors: detrended version of the handcrafted market factor is similar to the cummulative value of the first principal component, and the "oil sector factor" is similar to the cummulative value of the second principal component
- sometimes we can extracting "relevant" factors from a series of related measurements
- if there is a temporal or spatial relation of the input datapoints, the lower dimensionality projections can reveal something meaningful in relation with that dimension (time in our example), even if there is no visible clustering in the new subspace

Why dimensionality reduction

- sample Decision Tree on the 8-dim dataset used for the PCA example before, trained on 8 raw features and on 2 PCA components

- use extracted features in other machine learning algorithms rather instead of the raw input data
- applied a decision tree to the 8-dimensional dataset i previously presented, trying to predict the class of the points. The tree on the left was trained on the 8 dimensional raw data, while the tree on the right was trained only with the projections on the first two principal components
- we have both a simpler decision tree and higher accuracy for the tree on the right (which was run on the first 2 features extracted by PCA)
- unsupervised clustering algorithms can greatly benefit from running dimensionality reduction before being applied
- more robust learning (=works better when having noise or corner cases), less overfitting (=works better on unseen data), can mitigate "the curse of dimensionality"
- usually lower model complexity, can help interpretation and visualization
- performance increase on supervised tasks: better prediction models performance (one can replace the inputs or combine with projections, adding them as new features). When replacing the features, usually better accuracy at similar complexity
- boosted trees and random forests are less affected, but even there it can help when you struggle for few percents accuracy improvements
- still, beware of losing important low variance features with some techniques such as PCA (and try using also ICA to avoid that)

Why dimensionality reduction

- data compression
- why it works: successive data samples have some relation one to another

- a data point for each vertical line (so we have 768 points in a 512-dimensional space), and apply PCA to it, then we keep only few of these components: 5, 10 or 20
- reconstructing the original data using PCA requires us to know the coordinates of the projections for each point and the direction of the old axis in the new reference system. This means for example that when reconstructing the image from the first 5 principal components we'll need 768 points with 5 coordinates and the first 5 rows of 512 elements from the rotation matrix
- image compression with PCA does not make sense, but it's a nice example of how few factors are needed to build a meaningful reconstruction of the original data (however, other dim red techniques like autoeconders do a better job)
- when using the first 10 components we already have a good enough image to make sense of it. This means that with just a bit over 3% of the original information we have a good understanding of the data

Why dimensionality reduction

- noise removal and improved anomaly detection

- the 9 US stocks and applied PCA on their daily returns then marked the outliers at 99th percentile
- top-left chart 3 of the stocks are plotted with the outliers marked in the raw data. The red dots are the moments when the movement of a certain stock up or down was in top 1% as magnitude
- there is no good or bad method of looking at outliers, they just mean different things and they might be interesting depending on the problem you're trying to solve
- top-right chart shows outliers in the reconstructed data. Theoretically smoothed, free of noise that we consider irrelevant under the model's assumptions
- bottom-left chart shows outliers in the residuals. This means that we subtract the reconstruction from the original data and we look for the extreme "errors" that remain after applying our dimensionality reduction technique
- bottom-right chart shows the outliers in the factors. These are no longer tied to a certain column in our original data, so it's no longer tied to a stock, but rather to our newly extracted factors (interpretable or uninterpretable)
- this breakdown seems to complicate outliers detection instead of simplifying it, but actually allows looking at the problem from different angles

Feature selection

- feature selection vs feature extraction: dropping features vs creating new ones
- low variance filter
- correlation based filtering
- univariate feature selection
- recursive feature elimination
- variable importance based filtering

- selection is a "degenerate case" of dimensionality reduction: drops off irrelevant columns
- selection might help in obtaining better results, no matter the model, or improve the results of feature extracting methods (like PCA). Or maybe not
- low variance filter: simply remove constant or near-constant features. Use with caution, chart on the right example has the lowest variance for the generative factors
- correlation filtering is removing the features that are highly correlated to other columns, left chart example
- univariate selection: select top k features based on statistical tests against the output variable (such as ANOVA, chi-squared, mutual information)
- recursive feature elimination: [usually linear] fitting of all features against the output, then filter out low performers in an iterative fashion. It handles both low variance and colinear features
- selection by variable importance: beta as importance score for linear regression. Recommend tree ensambles
- use decision trees for non-linearity: depth as naive measure in decision tree. Information gain or decrease in gini impurity
- random forests (mean decrease in gini or mean decrease in accuracy: trained data vs out of bag) and boosted trees (count in splits divided by total splits or average gain across splits)

Linear Discriminant Analysis (LDA)

- supervised methods try to reduces the number of dimensions by trying to maximize the class separation
- LDA also computes a decision boundary, it can be used as a classifier
- projections to the first component have the highest class separation (LDA decomposition focus is separation, while PCA decomposition focus is correlation)

- bayesian classifier, computes decision boundaries so they also can be used to predict the class of unseen data points
- in order to achieve that linear separation, LDA makes the assumption that all the groups share the same covariance (this means that although the groups are different, how the predictor and target variables vary in relation to each other is similar across all groups)
- data needs to be linearly separable, does not work ok when means and variances are correlated
- although used for a different purpose, it has some similarity with MANOVA
- example on an 8-dimensional dataset, it does not quite satisfy the same covariance requirement because of the blue group, but it still worked ok. LDA makes a transformation of the data such that the first component allows the best linear separation of the classes, then the second dimension and so on
- Fished Discriminant Analysis - LDA with 2 classes, KFDA - kernel version for non-linear separation

Quadratic Discriminant Analysis (QDA)

- can be used as a classifier
- suitable for non-linearly separable data
- less assumptions about the distributions than LDA, QDA computes both means and covariance for each group

PCA

- when dropping components: projection to lower dimensional space
- the new axes define a lower dimensional subspace, the compressed dataset is built from the new coordinates of the projected points in this subspace

- PCA again. visualization is a better illustration of what dimensionality reduction by dropping features while retaining relevant information means
- PCA finds orthogonal vectors that allow writing the data as linear combinations of the basis. Or, reformulating, explains correlated data with fewer uncorrelated variables (and those variables are linear combinations of the originals)
- PCA explains variability, reduces correlation between axis and when dropping components, indirectly reduces entropy of the data
- closed form
- there is no assumption about the distribution in PCA, but works best when the signal is a linear combinations of factors, the factors are independent and orthogonal sources, the source factors are homoscedastic
- relation to Factor Analysis -> FA has no orthogonality constraint
- PCA will take as the first axis the one that maximizes the explained variance. A DT will split on a condition that maximizes the information gain or node purity (gini index)

PCA

- what to look at: the principal components, explained variance by axis, direction of initial vectors in the new subspace, datapoints projection, reconstruction (additive from contributions on each axis), estimated dimensionality

- scree plot: how much of the data variance is explained by each new axis. 3rd dimension explains very little, so it's a dimension that can be "safely" dropped
- estimated dimensionality: looking at the number of significantly positive eigenvalues or at cummulative percentage of explained variance (trap: noise can be a good part of the variance)
- the second plot: the direction of the new axis relative to the original cartesian reference system. eigenvectors = the new rotation/axes vectors, eigenvalues = explained variance
- third plot: the relation of the datapoints in the new reference system. individuals color heatmap: the importance of the principal component for the datapoint (square cosine = contribution of the component to datapoint's distance to origin)
- reconstruction: it's just a "change of basis" and without loss of information if the number of components is equal to the number of features
- "what to look at": mention also outputs for generative models, graphic representations of datapoints in the latent space, or (when clustering) average activations by feature

sparse PCA

- PCA vs sparse PCA: both are linear transformations, sparse PCA just another rotation
- iterative algorithm using shrinkage methods (lasso, ridge, elastic net)
- adds a regularization term to the loss function, penalizing non-zero coefficients

- yet another linear transformation, just like PCA, but which adds some sparsity constraints
- theoretically simpler, more interpretable features while the results should be similar to PCA
- 8-dimensional dataset example: both PCA and Sparse PCA produced very close results, but the table which tells how the principal components are built as linear combinations from the original dimensions differs. PCA has significant contributions from several dimensions, the Sparse PCA algorithm is basically selecting two of the existing dimensions as relevant and enough to explain the data
- sparse PCA: iterative algo, adds a regularization term, similarly how ridge or lasso regression work
- L1 (Lasso) or L2 (Ridge) regularization variants are common
- certain implementation allow specifing how many "relevant features" to be allowed in the principal components

Independent Component Analysis (ICA)

- ICA vs PCA - variance explaining and orthogonal features vs signal explaining and independent features
- iterative algorithms doing minimization of mutual information or maximization of non-gaussianity (negentropy or kurtosis)

- PCA: sources of variance with an orthogonality constraint, ICA: "signals" from which the data is built, usually without an orthogonality constraint. Two lines with different noise added, PCA finds the axis in the direction of variance, ICA finds our real source factors
- wide range of ICA algorithms available, some of the most used are FastICA, InfoMax, Jade (reconstruction, orthonormal, RADICAL)
- pre-processing of the data ("whitening", transforming to uncorrrelated and unit variance), main difference is in the optimized target
- Infomax variants: minimizing the mutual information, "how much information is obtained about a random variable by observing another variable". InfoGAN reference, trying to maximize mutual information between the input data and a small subset of the cells in the latent layer
- maximize non-gaussianity: negentropy as a measure of distance of a distribution to being gaussian. Mention why the normal distribution has the highest entropy from all distributions for a given mean and variance
- highly structured data vs noise - lower entropy = an "ideal world" has no information, higher entropy = noise, a lot of (maybe) useless information. Noise is hardest to reconstruct from projections, but also easy to generate (or something "with similar properties")
- a gaussian distribution maximizes disorder, easily described in parametric form, but a lot of bits needed to retain the information. All constituents have the same probability, none can have a shorter encoding. Maximizing the kurtosis: shape of the tails (high = few outliers, low =a lot of outliers). Excess kurtosis
- why the normal distribution appears, dices and markets example. Rigged dices. Jumps example, finding a projection of the data such that it becomes more ordered.

ICA

- ICA extracts "independent features", theoretically the reconstruction of original images should be better if they have low mutual information

PCA on non-linear data

- sometimes linear transformations are not enoguh

kernel PCA

- "kernel trick": a mapping function computing the similarities between points in a higher dimension in order to obtain better data separability, without actually knowing where the points are in the higher dimensional space
- linear, polynomial, spline, radial basis function (RBF), ANOVA RBF etc.
- a RBF kernel projects into an infinite dimensional space, it is way more complex than the 2D gaussian function on the right

- probably encountered kernels when playing with SVMs, but they can be used in a lot of contexts, including PCA or ICA
- "kernel trick": mapping similarities between points in a higher dimension, without actually doing the transformation and knowning where the datapoints lie in the higher dimensional space
- left image: 3 groups of points belonging to two classes. There is no line which we can draw in such a way that it separates the two classes, but they can be transformed to something like in the second image by warping the space, A4 page folding example
- many possible kernels, most common: linear, polynomial and the RBF. Any kernel can be used, including custom ones. The two dimensional gaussian function on the right as well. A RBF kernel is way more complex than that, as it projects in an infinite dimensional space
- kernel trick: computationally cheap, no need to represent in higher dimension first, which might be computationally intractable (or impossible to represent, as in RBF kernel case)
- no actual recipe, always experiment. For something like the example on this slide use a polynomial kernel. For sparse data, such as text, use a linear kernel and when the data is smooth, try a RBF kernel.Finding the right kernel is tricky and using custom kernels possible, but not likely. Autoencoders: in a way finding "a good kernel" automatically

kernel PCA

- maps points without making a projection, it just computes a dot-product between points "as if"" they were from a higher dimension
- kernel parameters tuning: various methods, usually grid search
- models incorporate external knowledge when applying a certain kernel or technique (including by the choice of the parameters)

- kernels have parameters and you'll need to tune then in order to improve your results
- animations show the results of applying a RBF kernel PCA on the two datasets, the concentric circles and the S shape, to show the impact of the sigma parameter
- by applying a certain kernel you're actually embedding knowledge about the problem in your model. Also the choice of kernel's parameters is "external knowledged" that you put in your model
- a RBF kernel has a single parameter, while polynomial kernels have more
- some kernel calculation times increase with the size of the dataset (RBF quadratic)
- searching the values of kernel parameters is also an open question. Usually k-fold cross validation and a grid search or, if you have many parameters, strategies used for any black box optimization: greedy, simulated annealing, genetic algos, gradient descent, random jumps with hill climbing, tabu search etc.

Multidimensional Scaling (MDS)

- non-linear transformation, applied on distances (can be non-euclidian)
- transforms the proximity metric to fitted distances in a lower dimensional space, such that the disparities are mapped as good as possible
- preserves topology

- MDS: non-linear technique used for visualization before algorithms like SNE or UMAP appeared
- applied on distances between points rather than on the points themselves. It operates with the relation between datapoints and not on their values. Any kind of distances can be passed to the algorithm, but it's common to apply them on euclidean distances
- multiple variants of the algo, main idea is transforming the proximity measures we pass to it to fitted distances in a lower dimensional space in such a way that the disparities (not the similarities) between the original points are mapped as good as possible in the projected space
- standard MDS: eigendecomposition on the squared proximity matrix
- nonmetric MDS: iterative, starts with an arbitrary initialization in the lower dimensional space, minimizes a cost function measuring how well disparities are fitted ("Kruskal's stress-1 index", values <0.05 are considered "good")
- distance between projected points is no longer euclidian, is a measure of sample similarity. Axes are arbitrary, no longer interpretable, they are not "principal components" in a standard sense. No orthogonality constraint
- MDS, like autoencoders, is not necessarily projecting in lower dimensions, they could as well find a "better" representation in a higher dimensional space
- quite sensitive to the random initialization. Needs "remapping" if the dataset changes, any new point needs re-running the algorithm

IsoMap

- Isometric Feature Mapping Ordinationhttps://web.mit.edu/cocosci/Papers/sci_reprint.pdf
- uses "geodesic" distances: retains only some of the graph distances among objects (the smaller ones) and estimates all dissimilarities as shortest path distances

The S curve fit shown above is not necessarily a good example, IsoMap is more helpful when having many dimensions

Locally Linear Embedding (LLE)

- finds neighbours, computes the weights that best reconstruct the points from its neighbors as linear combinations, map to embedded coordinates by computing the best reconstruction from those weights
- "think globally, fit locally"http://www.jmlr.org/papers/volume4/saul03a/saul03a.pdf

- overlapping local neighborhoods, when collectively analyzed, can provide information the about global geometry
- assume we have a dataset with points from a 3D shape, first we find neighborhoods of points, then we take a sheet of A4 paper and move it around, projecting these points on it, and finally we re-assemble these projections in some special way, we obtain a lower dimensional representation of the data. Reformulation: cutting some linear patches on which we projected our neighborhoods and reassemble them such that we preserve the angles formed by each datapoint to its neighbors
- has a single parameter, the number of neighbors, and that we have a guarantee of global optimality. This number of neighbors is an indirect measure of how much of the global structure is retained
- works best if the original data is locally linear (a 3D S leter with no perturbation)
- (LLE has a dynamic number of neighborhoods while SOM has a fixed one)

Linear Latent Tangent Space Alignment (LLTSA)

- LTSA varianthttps://www.sciencedirect.com/science/article/pii/S0925231206004577
- computes nearest neighbors, finds a tangent space to each neighborhood and combines those to find an embedding that aligns the tangents

t-SNE

- Stochastic Neighbor Embedding varianthttp://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf
- measures similarity between points by converting euclidian distances to probabilities according to the normal distribution, then tries to minimize the similarities in the projected space (using KLD) according to a t-distribution
- has a cost function that includes an attractive force and a repulsive one, optimized using gradient descent

- t-SNE: mainly used for visualization, became almost standard in the past years for data exploration
- converts euclidean distances between datapoints to a normal distribution, then projects the points to a lower dimension trying to minimize the similarities in the projected space according to a t-distribution, using Kullback-Leibler Divergence
- KLD: one of the many ways to measure the difference between two distribution. "how much information is lost when approximating one distribution with another" or "how much a sample helps - on average - to distinguish between two distributions"
- difference between t-SNE and the original SNE algorithm is that it uses a student t-distribution in the latent space. Why the t-distribution: it has fatter tails and allows a nice spreading of the data, the projected points get nicely repelled and this circumvents the crowding problem
- Perplexity matters, the lower the value the more "local relation" between datapoints matters, while a higher value is a kind of zoom-out. An indirect measure of the optimal size of the neighborhoods t-SNE would like to preserve the structure for. Beware of "false clustering": t-SNE's job is to produce neighborhoods
- t-SNE is non-parametric and it does not create a mapping function. Needs re-run when adding points and results can be different
- PCA is mapping euclidean distances, MDS is mapping similarities and t-SNE is mapping joint probabilities. Compared to autoencoders, t-SNE is preserving the neighborhood probabilities, while autoencoders minimize the reconstruction error

UMAP

- Uniform Manifold Approximation and Projectionhttps://arxiv.org/abs/1802.03426
- much faster, has similar or better results than t-SNE and can transfer learning (can be used to predict)
- preserves more of the global structure

- a more recent method recommended over t-SNE
- beautiful piece of modern mathematics and its applications in machine learing, it moves from probabilities like in t-SNE to affinities, and from fixed neighborhoods to fuzzy topological representations of the data
- instead of belonging to a neighborhood, the datapoints have probabilities of being part of a simplex (which is a generalization of a triangle in N-dimensional space), then optimizes the lower dimensional representation by minimizing the cross-entropy of the two fuzzy sets, in the original representation and in the lower dimensional space
- the arguments for using it is that it's much faster than t-SNE, has similar or better results than t-SNE, it preserves more of the global structure and can transfer learning, which means that it can predict a representation in the lower dimensional space for unseen datapoints

t-SNE vs UMAP

- MNIST dataset visualization

Self Organizing Maps (SOM)

- a type of neural network mapping high dimensional data to a fixed grid of cells, preserving the topology
- very nice for data exploration, even when having few features (fallen out of favor recently, but remains a powerful technique)

- clustering, dimensionality reduction and nice visualizations at the same time. Preserves the topology, neighbourhood relation kept in latent space
- the only image in the presentation that was generated using an external tool. Presentation code contains a commented example that produces similar results, but the Peltarion visualization is nicer
- SOM: mapping each datapoint to a fixed two dimensional grid using an iterative algorithm. Starts with a random initialization (to which the algorithm is sensitive), tries to build neighborhoods: for each cell in the latent space a Best Matching Unit and a radius of the neighborhood get gradually updated, warping this fixed two dimensional grid to the input space. Somehow like throwing a fish net made of elastic such that it best covers the original data
- grayscale chart is a "unified distance matrix", shows the average distance between the datapoints that ended up in that cell, a measure of crowding
- the size of the black point: the number of datapoints in the neighborhood, the bigger the black point in the cell, the more points in it
- heatmaps visualize the average value of each feature in our dataset in this grid. Side-by-side representations can emphasise relations
- wines and their properties example: there's little overlapping between the high values in the bottom-right Quality feature and high values in ResidualSugar feature on the middle-left. Linear regression could tell that also, but SOMs make it easier to see relations
- by the size of the black dots we can estimate that a lot of the wines that were labeled as having lowest quality have pretty high volatile acidity

Visualization done with Peltarion Synapse (unfortunately discontinued), still available as an online platform

Autoencoders

- easy to implement, harder to interpret
- all tunings of neural networks apply to autoencoders: topology, cost function, type of layers, type of cells, type of activation functions, number of nodes, regularization, skip connections, dropout/dropconnect, optimizers, network initialization
- use convolutions when there is some spatial relation, [maybe] recurrent networks for time-series

- this slide shows the actual activity of a single layer autoencoder which learns to represent in 2 variables a linear relation between the inputs. Given these 2 values, the decoder is able to reconstruct the input
- components: an encoder, that transforms the inputs to a different representation of the data, the latent layer which holds that representation, and the decoder which reconstructs the inputs as good as possible.
- reconstruction error metric to use: it depends on the distribution of your data, but it's common to use the mean squared error and pre-process your input data using scaling, box-cox power transform or logarithmation
- all neural nets tunings apply to autoencoders. Including transfer learning, warming up classification networks with autoencoders or vice-versa
- the AE will store knowledge about the problem, allowing a representation that should help find structure in the data and allow simpler representations of it
- a myriad of variants of autoencoders, we'll briefly take a look at few variants
- applying an autoencoder is an easy solution when you don't know or don't care about the structure of the inputs and we don't mind too much about interpretability of your mappings
- this "interpretability" and "disentanglement" of underlying factors is a nice area where there's a lot of research happening

Autoencoders

- sample with highly correlated input features: hue coding with a simple one layer autoencoder
- 150 input features, 1000 samples

Autoencoders vs PCA vs ICA

- autoencoders are better at recovering the original features and the interaction between them
- why not always use autoencoders? sample size needed, overfitting dangers, lots of tuning needed, interpretability

- what we get when applying different methods on that input data. The data is not noisy and it's well structured, recovering the signal should be easy
- in the top-left corner you have the original signal and the interaction between the generating factors
- in the top-right corner you have what PCA recovered and the plot with the interaction between the first two principal components. PCA recovered the sinusoidal nature of the signal and a rotation of the interaction, but likely because our data is heteroskedastic what we have is not our generating factors
- bottom-left chart is the ICA result, which recovered pretty well the interaction of the generating factors, but the factors themselves are again not close to the originals. They still have the sinusoidal nature, but they lost one of their properties which was that their variability was constant over time
- the bottom-right corner shows the reconstructions from the shallow AE, which caught the nature of the generating factors and the interaction
- there is no good or wrong dimensionality reduction, they just extract different things from the signal. Try different algorithms
- shallow linear AE work almost as PCA, but they extract vectors are not orthogonal and variance tends to be equally distributed across latent variables
- always try visualizing what your network learns. Here we have one chart showing the activations plotted against the sample index, and one chart is showing the activations in the first node in the latent layer plotted against the activations in the second node (just like we plotted for PCA and ICA the projections on the first component against the projection on the second component)

Deep Autoencoders

- multiple layers, usually with a symmetric hourglass topology
- latent layer in the middle

- back to the concentric circles and the S-shape datasets and show the results of running a deep AE on them. A deep AE is just a network with multiple layers, usually (but not necessarily) in an hourglass shape with the number of cells per layer gradually decreasing until the latent layer, then gradually increasing in a symmetric fashion until the output layer
- top row shows how using AE we can expand the representation from 2D to 3D, hoping for better data separation, so we can use them to increase dimensionality if that explains the data better
- easy solution when you don't know or don't care about the structure of the inputs. lots of data: AE, less data: go with "traditional" robust techniques
- work best with lots of data: check the number of parameters. Experiment with activations, sometimes ReLu not suitable, replace with LeakyReLU, Tanh, ELU, sigmoid. Can be sensitive to initial conditions (and to a lot of parametrizations)
- fast convergence using optimizers like adam/Nadam (shallow networks have usable results after ~15 epochs)
- can be used as warmup for other classifier networks (and the other way around). A network that is able to condense the data should, in theory, classify better. However, beware of smoothing/averaging - details can be lost. Side note: ensembles work better most of the time)

Sparse Autoencoders

- adds a penalty for multiple activations
- reconstruction results will be similar, the difference is in the sparsity of activations and, thus, robustness and interpretability
- theoretically forces better data separation by repelling different samples in the latent space

- adds sparsity constraints. Add a penalty term to force only few cells to be activated. This encourages learning of different features by different neurons
- this can be combined with shallow or deep autoencoders. Slide example is a sparse deep autoencoder
- the fact that sparse activations are encouraged are visible in the charts, you can see in the "Node vs node" charts how the points are spread closer tot the axis
- the distribution of activations in the rightmost charts: with red are the sorted average activations in the latent layer for the autoencoder from the previous slide and with blue the activations of the sparse autoencoder. By the shape of the S curve you see that the sparse autoencoder has a tendency of being under or over activated when compared with a regular one
- can be also combined with convolutional layers or recurrent cells

Stacked Autoencoders

- chaining encoders and decoders, can be seen as a series of resampling downward/upward

Denoising Autoencoders

- based on a simple data augmentation trick: add noise to inputs while keeping the originals as output
- increased robustness
- projections sample is for MNIST

- simple trick that's also common for data augmentation: we adds noise to the inputs when training, while we expect to reconstruct the clean version
- increases the robustness of the model, it becomes less sensitive to noise and theoretically learns better representations of the data
- example is for a shallow denoising autoencoder trained on the MNIST dataset and trained 3 cells in the latent layer, and i feed the digits to the network as vectors of 784 values from 0 to 1. Each digit from 0 to 9 has a different color. We have a single layer and no convolutions: the autoencoder is separating the digit classes
- note: we also see from this chart that the activations tend to have this diagonal form, which means that the cells activations are correlated. In other words, they fire up together, which is generally not such a good thing, because we would like, as much as possible, to have our autoencoders discover independent factors. Changing the activation function or adding sparsity constraints might help
- another trick, which i haven't used here and some people deploy to improve learning is to drop parts of the input and force the autoencoder to reconstruct the full input, basically forcing signal recovery from partial measurements
- AE samples are quite shallow, better results can be obtained when working with images by adding convolutional layers

Contractive Autoencoders

- a type of regularized autoencoders
- only the loss function differs, it will penalize sensitivity of latent activations to inputs
- can be combined with other types (sample projection is for denoising-contractive AE)

Variational Autoencoders (VAE)

- variational autoencoders - discovering latent factors via variational inference
- latent space is special, stores probability distributions (for each dimension a mean and a standard deviation is kept). Decoder samples from a normal distribution in the latent layer. The "reparametrization trick" allows the autoencoder to backpropagate
- semi-supervised extension: cVAEhttps://arxiv.org/abs/1406.5298

- finally got to the most interesting class of autoencoders: the ones that do variational inference, a method of approximating probability densities
- in the charts above we have the activations of the 3 cells in the latent layer of a variational autoencoder with dense connections and an intermediate layer of 50 cells. So we have just 50 cells plus our latent layer and we input raw pixel data, without having any convolutions
- best data separation from the autoencoders presented so far, some classes are close to have bivariate normal representation, meaning that our network learns factors which are close to independent random variables
- how do these variational autoencoders work: their latent space is special, instead of keeping a value like regular autoencoders, they keep probability distributions. So for every latent dimension we actually keep two values, one with a mean and one with a standard deviation (encoder is an inference network)
- in addition to the reconstruction loss (the negative log likelihood), we have a special KLD term which encourages the gaussianity of the latent variables
- this has a side effect for example that we end up having representations of various rotations of the digit 7 close one to another in the latent space. Or makes 8 more likely to be close to 6 and 9. We assume the latent data manifold has representations normally distributed
- VAE is a variational lower bound estimator, maximizing encodings PDF area under an assumption of a normally distributed latent manifold. At decoding time we're Monte Carlo sampling from the normal distributions in the latent layer, then backpropagate the error. "Reparametrization trick" to allow differentiation

VAE

- latent space representation and manifold traversal (note: 2 layers and only 3 (x2) cells in the latent layer)

- on the left we have the MNIST dataset activations of the 3 dimensions in the latent layer. Probably i should have sticked with two dimensional representations, but the data separation increased significantly and it's more visible in 3D
- what we plot here are the mean values we get in the latent layer when we feed the input values
- the decoder is a function building the data distribution from a combination of isotropic gaussian factors
- in the right side: a generative traversal of the latent space. A grid of values from the normal distribution passed to the decoder
- it should be mentioned again that this is an output from a quite simple dense network, not from a convolutional network
- notice is that we obtain what we expected, representations of a 7 are close to a 1 or to a deformed 9, or 6 is close to 8
- another thing visible is the blurriness of the generated samples. This is because autoencoders in general and variational autoencoders especially have a tendency of learning averaged representations, while generative networks have in their training objective the condition that samples have to look like being from the real distribution
- adding CNN layers would significantly improve the performance

beta-VAE

- beta-VAEhttps://openreview.net/forum?id=Sy2fzU9gl: a step towards interpretability - tries to disentangle the latent factors (in an ideal representation single latent units are sensitive to single generative factors)
- how beta works: simple multiplication in the VAE objective function, which seems to encourage the latent representation axes to be sensitive to changes in generative factorshttps://arxiv.org/abs/1804.03599

- interesting empirical finding for people still try to find a theoretical justification. Some people at DeepMind, probably randomly experimenting, ended up finding that if you simply multiply the KL Divergence term of the VAE loss, you end up with more interpretable factors extracted
- beta = how much the KLD term matters in the loss function. More weight to the constraint of having normally distributed activations in the latent layer
- links to the original article and to one that tries to explain why disentanglement happens
- beta-VAE is building a representation that should still be sufficient to perform reconstruction while imposing a constraint on the amount of information it holds (and the constraint tightens as beta increases)
- original article: encoding bitmap representations of chairs, certain cells encoded factors like the chair size, the size of the chair back or the leg type
- a lot of objections to this beta, simply put it cannot be that simple, just multiply by a number and get meaningful factors. And indeed the world proved to be more complex and in a lot of cases the extracted factors were not interpretable
- improved versions: Total Correlation-VAE decomposes the beta-VAE loss adding a new metric measuring disentanglement based on mutual information. Independent Subspace Analysis-VAE changes the prior distribution of the latent variables, instead forcing gaussianity it allows different types of distribution (remember non-gaussianity optimization in ICA) and can be combined with beta and TC variants. Other promising variants in the references

beta-VAE

- activations and traversal for the MNIST dataset: 2 layers network and only 3 (x2) cells in the latent layer

cVAEGAN

- Generative Adversarial Networks: great for generating plausible highly detailed data from the distribution, while autoencoders learn averaged representations
- cVAEGAN: semi-supervised, conditional learning
- combining multiple networks, some with common layers: encoder, decoder, classifier and discriminator

- another approach to meaningful dimensionality reduction and extraction of disentangled factors was to go for semi-supervised models, to train a classifier and feed that classifier's output to the latent layer, together with the original input
- another development is combining a network with a classifier like described (called conditional-VAE, and which can be used on its own) with an adversarial network
- generative adversarial networks: the idea there is to have a network called generator that is producing outputs that look as close as possible to the data it sees, and another network called discriminator that tries to tell when the data is from the real distribution and when it's a fake generated by us. This arms race theoretically improves the results of both networks if they converge
- combining a cVAE with in this adversarial yields the conditional-VAEGAN, which is a network built from 4 sub-networks, some with common layers: an encoder, a decoder, a classifier and a discriminator
- references have a link to IFcVAEGAN, a promising extension which adds what they call information factorization on top of it (learning to generate a certain sample with or without some attribute)
- stability problems: combining the reconstruction loss with the adversarial loss is tricky, they might not converge. Poor results on highly variable datasets

cVAEGAN

- convolutional layers, only 3 cells in the latent layer

Uncertainty Autoencoder (UAE)

- Uncertainty Autoencodershttps://arxiv.org/abs/1812.10539: adding noise in the latent layer
- tries to find a sparse representation of the original data that best allow reconstruction, maximizing the mutual information between the data points and a noisy representation in the latent layer

- an interesting recent development which tries to find sparse representations of the original data that best allow reconstruction by maximizing the mutual information between the inputs and some noisy representations in the latent layer
- simple but efficient trick: at decoding time there's noise added in the latent layer. This encourages learning a meaningful representation, the autoencoder learns a generative model, although it does not have an explicit likelihood function
- interesting connection between UAE and compressed sensing. Side note, an extreme example of compressed sensing is the "single pixel camera": a camera with a single sensor can reproduce the original image given a small enough number of measurements if they are done by illuminating (or redirecting light using mirrors) different areas of the space
- optimizing an amortized variant of the variational lower bound
- interesting connection with PCA, they show techniques are equivalent in the presence of high noise
- UAE outperforms consistently PCA when training classifiers on top of PCA or UAE features

UAE

- data separation is already good, although reconstructions don't look so well
- sample network is small, embedding more knowledge in it can help: deeper networks, more neurons, convolutions

Recurrent autoencoders

- the input and the output is a sequence
- using special cells: GRU, LSTM, Nested LSTM
- long term dependencies problem: Bi-LSTM, attention. Maybe "attention is all you need".

Data source: https://www.ncdc.noaa.gov/ghcn-daily-description

- problems: longer time dependencies are hard to be learned, due to gradient propagation problems. Things vary a lot, after few hundred or even tens of samples is can be hard to learn dependencies. More training epochs needed
- the solutions people deploy for long term dependencies are inherited from natural language processing: Bi-LSTMs, which feed the same samples to two networks, one "as usual" and one in reverse order and combining their latent layers, or an attention mechanism
- attention is just another network, usually a shallow fully connected layer, which learns what samples from the recent past to feed to the recurrent network, and this "context vector" is passed to it together with the input
- "Attention is all you need" syntagm from an article published a year ago: discarded recurrent units entirely and showed (for a natural language model) that a simple attention model can outperform a recurrent network
- takeout: if you know something about how your time dependency behaves, it might be the case that you don't need a recurrent autoencoder: for example if you a process where the time dependency is decaying exponentially, rather than feed fixed samples to a recurrent network, it might be better to produce a normalized unevenly spaced vector of values, with the window increasing as you go in the past, and feed it as input to a non-recurrent autoencoder
- example is for a dataset with daily temperatures from 20 US cities. Charts show how the temperatures look like overall, for a certain city or across cities

Recurrent autoencoders

PCA again

Many more

- Nonnegative Matrix Factorization (NMF)
- Neighbourhood Components Analysis (NCA)http://www.cs.toronto.edu/~fritz/absps/nca.pdf
- Maximum Variance Unfolding (MVU)http://cseweb.ucsd.edu/~saul/papers/nldr_aaai06.pdf
- Generative Topographic Mappinghttps://www.microsoft.com/en-us/research/wp-content/uploads/1998/01/bishop-gtm-ncomp-98.pdf
- Diffusion Mapshttp://inside.mines.edu/fs_home/whereman/talks/delaPorte-Herbst-Hereman-vanderWalt-DiffusionMaps-PRASA2008.pdf
- Twin Kernel Embedding (TKE)https://www.researchgate.net/publication/5289090

Many more

- Deep Belief Networks and Deep Bolzmann Machines as autoencoders alternative
- Conditional Subspace VAE (CSVAE)https://arxiv.org/abs/1812.06190
- Vector Quantised VAE (VQ-VAE)https://arxiv.org/abs/1711.00937
- Total Correlation VAE (beta-TCVAE)https://arxiv.org/abs/1802.04942
- Independent Subspace Analysis VAE (ISA-VAE)https://openreview.net/forum?id=rJl_NhR9K7
- Factorized Action VAE (FAVAE)https://arxiv.org/abs/1902.08341
- FactorVAEhttps://arxiv.org/abs/1802.05983
- oi-VAEhttps://arxiv.org/abs/1802.06765
- Auto-Classifier-Encoder (ACE)https://arxiv.org/abs/1508.06585
- InfoGANhttps://arxiv.org/abs/1606.03657
- Adversarial Information Factorization (IFcVAEGAN)https://arxiv.org/abs/1711.05175